package com.hyb.algorithm.data.struct.tree;

/**
 * @Author: huyanbing
 * @Date: 2021/9/3 7:03 下午
 */
public class CountNodes {


    public int countNodes(TreeNode root) {

        if (root == null) {
            return 0;
        }

        int lh = 0;
        TreeNode left = root;
        while (left != null) {
            left = left.left;
            lh++;
        }

        int rh = 0;
        TreeNode right = root;
        while (right != null) {
            right = right.right;
            rh++;
        }

        //如果左右子树高度相等，则是一颗满二叉树
        if (lh == rh) {
            return (int) Math.pow(2, lh) - 1;
        }

        // 如果左右子树高度不相等，则按普通二叉树的高度计算
        return 1 + countNodes(root.left) + countNodes(root.right);
    }
}
